function generateRadomNumber(n) {
    const returnData = [];
    for(let i = 0; i < n; i++) {
        returnData.push(Math.floor(Math.random()*100));
    }
    return returnData;
}

const arr = generateRadomNumber(10);
console.log(arr);

//归并排序算法
function mergeSort(array) {
    if(array.length < 2) {
        return;
    }
    else {
        let step = 1;
        let left, right;
        while(step < array.length) {
            left = 0;
            right = 0 + step;
            while(right + step <= array.length) {
                mergeArray(array, left, left + step, right, right + step);
                left += step;
                right += step;
            }
            if(right < array.length) {      //这里是为了余出来的这部分数组
                mergeArray(array, left, left + step, right, array.length);
            }
            step *=2;
        }
        return array;
    }
}

function mergeArray(array, leftStart, leftEnd, rightStart, rightEnd) {
    const leftArray = array.slice(leftStart, leftEnd);
    const rightArray = array.slice(rightStart, rightEnd);
    leftArray.push(Infinity);
    rightArray.push(Infinity);      //添加哨兵值的目的是为了在其中一个数组用完元素后作为临界值判断
    let m = 0, n = 0;
    for(let i = leftStart; i < rightEnd; i++) {
        if(leftArray[m] < rightArray[n]) {
            array[i] = leftArray[m];
            m++;
        }
        else {
            array[i] = rightArray[n];
            n++;
        }
    }
};

console.log(mergeSort(arr));


//快速排序
function quickSort(array) {
    if(array.length === 0) {
        return [];
    }
    else if(array.length === 1) {
        return array;
    }
    else {
        const benchMarkIndex = 0;
        const benchMark = array[benchMarkIndex];
        const leftArray = [];
        const rightArray = [];
        array.forEach((item, index)=> {
            if(index !== benchMarkIndex) {
                if(item <= benchMark) {
                    leftArray.push(item);
                }
                else {
                    rightArray.push(item);
                }
            }
        });
        return [...quickSort(leftArray), benchMark, ...quickSort(rightArray)];
    }
};

console.log(quickSort(arr));